BOJ_2493_탑

앞에 있는 탑 중 현재 탑보다 큰 탑에 부딪히는 문제

Stack을 사용하여 앞선 탑들을 탐색함과 동시에 앞에 있는 탑이 현재 탑보다 키가 작다면 뒤에올 탑들에겐 보이지 않기 때문에 pop()으로 뺴버리는 것이 시간 단축의 핵심!

처음에는 list를 만들어 list의 indexOf()를 사용해 부딪힌 탑의 위치를 반환하도록 했는데, 시간 초과가 떴다

부딪힌 탑을 찾을 때마다 매번 리스트에서 인덱스를 찾는 것은 비효율적
-> Stack의 자료형을 Integer 대신 int[]를 줘 인덱스와 높이를 동시에 받게 수정하였다

출력 형식이 2 1 4 5 ... 이런 식이기 때문에 배열이나 리스트 대신 StringBuilder를 써서 출력하기 좋게 하였다

package BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Stack;  
import java.util.StringTokenizer;  
  
public class BJO_2493_탑 {  
  
    public static void main(String[] args) throws IOException {  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       int N = Integer.parseInt(br.readLine());  
       StringTokenizer st = new StringTokenizer(br.readLine());  
  
       Stack<int[]> stack = new Stack<>();  
  
       StringBuilder sb = new StringBuilder();  
  
       for (int i = 0; i < N; i++) {  
          int k = Integer.parseInt(st.nextToken());  
  
          while (true) {  
             if (stack.isEmpty()) {  
                sb.append('0').append(' ');  
                break;  
             }  
  
             if (stack.peek()[1] > k) {  
                sb.append(stack.peek()[0]).append(' ');  
                break;  
             } else {  
                stack.pop();  
             }  
          }  
          stack.push(new int[]{i + 1, k});  
       }  
  
       System.out.println(sb);  
    }  
}

#stack